import java.util.HashMap;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description: leetcode: 264. 丑数 II
 * <a href="https://leetcode.cn/problems/ugly-number-ii/description/">...</a><p>
 * User: DELL
 * Date: 2023-11-04
 * Time: 22:18
 */
public class Solution {
    /**
     * 解法一: (堆+哈希去重)
     * 丑数的本质为 num = 2^a * 3^b * 5^c
     * 总体思路就是使用小根堆，最开始先将 1 存入小根堆中，之后依次取出堆顶元素，
     * 然后再将取出来的元素乘 2，3，5后，依次加入堆中，然而这样子肯定会有重复，
     * 那么就是用一个哈希表来去重即可。
     * 其中的两个优化就是哈希表的 value 选用空间较小的boolean可以省空间
     * 另一个就是可能出现数字超出 int 能表示的范围，导致出现负数，而使得结果
     * 出错，而因为题目中的范围正好对应的是int能表示的丑数的极限，不会超出int
     * 的范围，而我们是将其乘 2，3，5后，可能超出范围，因此对超出范围的直接
     * 无视即可。
     * 时间复杂度:O(NlogN)
     * 空间复杂度:O(N)
     *
     * @param n
     * @return
     */
    public int nthUglyNumber(int n) {
        if (n <= 0) {
            return -1;
        }
        int[] arr = new int[]{2, 3, 5};
        // 辅助堆
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        // 辅助哈希表(这里其实Map第二个字段没用，因此直接置为较小的布尔值)
        HashMap<Integer, Boolean> hashMap = new HashMap<>();
        // 先将 1 入堆和哈希表
        heap.add(1);
        hashMap.put(1, false);
        while (--n != 0) {
            int temp = heap.poll();
            // 将 2*temp, 3*temp, 5*temp 均入堆和哈希表
            for (int i = 0; i < arr.length; i++) {
                // 这里校验一下是否新入的值超出 int 的范围，超出的直接无视
                if (temp > Integer.MAX_VALUE / arr[i]) {
                    break;
                }
                if (!hashMap.containsKey(arr[i] * temp)) {
                    hashMap.put(arr[i] * temp, false);
                    heap.add(arr[i] * temp);
                }
            }
        }
        return heap.poll();
    }

    /**
     * 解法二: (动态规划)
     * 首先假设 dp[i] 为第 i 个丑数，那么dp[1] = 1，同时有如下推理
     * 1.丑数dp[i]一定是比dp[i]小的某个丑数dp[x]乘以2/3/5的结果；因此通过对
     * 已有的丑数进行乘2/3/5遍历，我们可以得到逐步得到所有丑数；
     * 2.我们分别用三个指针p2/p3/p5记录下最后一个没有进行过乘2/3/5操作的丑数，
     * 即比p2/p3/p5的丑数小的丑数都已经进行了乘2/3/5的操作，已经记录到了丑数
     * 数组里，大于等于p2/p3/p5的丑数尚未进行乘以2/3/5的操作，不在丑数数组中；
     * 那么dp[p2]*2, dp[p3]*3, dp[p5]*5的最小值一定就是下一个丑数dp[i]
     * 3.对于dp[px]*x == dp[i]的被选中的指针px，由于该指针已经进行了乘法操作，
     * 因此需要+1指向下一个未进行该乘法操作的丑数，用于选取dp[i +1]
     * 4.对于dp[px]*x > dp[i]的指针px，由于其值大于dp[i]，因此px指针仍可以
     * 用于dp[i+1]的选取
     *
     * @param n
     * @return
     */
    public int nthUglyNumber2(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        int p2 = 1;
        int p3 = 1;
        int p5 = 1;
        for (int i = 2; i < dp.length; i++) {
            int num2 = dp[p2] * 2;
            int num3 = dp[p3] * 3;
            int num5 = dp[p5] * 5;
            dp[i] = Math.min(num2, Math.min(num3, num5));
            if (num2 == dp[i]) {
                p2++;
            }
            if (num3 == dp[i]) {
                p3++;
            }
            if (num5 == dp[i]) {
                p5++;
            }
        }
        return dp[n];
    }
}
